﻿using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;

namespace Gimela.Media.Imaging
{
  /// <summary>
  /// 各种块计数算法的基类
  /// </summary>
  /// 
  /// <remarks><para>The class is abstract and serves as a base for different blob counting algorithms.
  /// Classes, which inherit from this base class, require to implement <see cref="BuildObjectsMap"/>
  /// method, which does actual building of object's label's map.</para>
  /// 
  /// <para>For blobs' searcing usually all inherited classes accept binary images, which are actually
  /// grayscale thresholded images. But the exact supported format should be checked in particular class,
  /// inheriting from the base class. For blobs' extraction the class supports grayscale (8 bpp indexed)
  /// and color images (24 and 32 bpp).</para>
  /// 
  /// <para>Sample usage:</para>
  /// <code>
  /// // create an instance of blob counter algorithm
  /// BlobCounterBase bc = new ...
  /// // set filtering options
  /// bc.FilterBlobs = true;
  /// bc.MinWidth  = 5;
  /// bc.MinHeight = 5;
  /// // process binary image
  /// bc.ProcessImage( image );
  /// Blob[] blobs = bc.GetObjects( image, false );
  /// // process blobs
  /// foreach ( Blob blob in blobs )
  /// {
  ///     // ...
  ///     // blob.Rectangle - blob's rectangle
  ///     // blob.Image - blob's image
  /// }
  /// </code>
  /// </remarks>
  /// 
  public abstract class BlobCounterBase
  {
    // found blobs
    List<Blob> blobs = new List<Blob>();

    // objects' sort order
    private ObjectsOrder objectsOrder = ObjectsOrder.None;

    // filtering by size is required or not
    private bool filterBlobs = false;
    private IBlobsFilter filter = null;

    // coupled size filtering or not
    private bool coupledSizeFiltering = false;

    // blobs' minimal and maximal size
    private int minWidth = 1;
    private int minHeight = 1;
    private int maxWidth = int.MaxValue;
    private int maxHeight = int.MaxValue;

    /// <summary>
    /// Objects count.
    /// </summary>
    protected int objectsCount;

    /// <summary>
    /// Objects' labels.
    /// </summary>
    protected int[] objectLabels;

    /// <summary>
    /// Width of processed image.
    /// </summary>
    protected int imageWidth;

    /// <summary>
    /// Height of processed image.
    /// </summary>
    protected int imageHeight;

    /// <summary>
    /// Objects count.
    /// </summary>
    /// 
    /// <remarks><para>Number of objects (blobs) found by <see cref="ProcessImage(Bitmap)"/> method.
    /// </para></remarks>
    /// 
    public int ObjectsCount
    {
      get { return objectsCount; }
    }

    /// <summary>
    /// Objects' labels.
    /// </summary>
    /// 
    /// <remarks>The array of <b>width</b> * <b>height</b> size, which holds
    /// labels for all objects. Background is represented with <b>0</b> value,
    /// but objects are represented with labels starting from <b>1</b>.</remarks>
    /// 
    public int[] ObjectLabels
    {
      get { return objectLabels; }
    }

    /// <summary>
    /// Objects sort order.
    /// </summary>
    /// 
    /// <remarks><para>The property specifies objects' sort order, which are provided
    /// by <see cref="GetObjectsRectangles"/>, <see cref="GetObjectsInformation"/>, etc.
    /// </para></remarks>
    /// 
    public ObjectsOrder ObjectsOrder
    {
      get { return objectsOrder; }
      set { objectsOrder = value; }
    }

    /// <summary>
    /// Specifies if blobs should be filtered.
    /// </summary>
    /// 
    /// <remarks><para>If the property is equal to <b>false</b>, then there is no any additional
    /// post processing after image was processed. If the property is set to <b>true</b>, then
    /// blobs filtering is done right after image processing routine. If <see cref="BlobsFilter"/>
    /// is set, then custom blobs' filtering is done, which is implemented by user. Otherwise
    /// blobs are filtered according to dimensions specified in <see cref="MinWidth"/>,
    /// <see cref="MinHeight"/>, <see cref="MaxWidth"/> and <see cref="MaxHeight"/> properties.</para>
    /// 
    /// <para>Default value is set to <see langword="false"/>.</para></remarks>
    /// 
    public bool FilterBlobs
    {
      get { return filterBlobs; }
      set { filterBlobs = value; }
    }

    /// <summary>
    /// Specifies if size filetering should be coupled or not.
    /// </summary>
    /// 
    /// <remarks><para>In uncoupled filtering mode, objects are filtered out in the case if
    /// their width is smaller than <see cref="MinWidth"/> <b>or</b> height is smaller than 
    /// <see cref="MinHeight"/>. But in coupled filtering mode, objects are filtered out in
    /// the case if their width is smaller than <see cref="MinWidth"/> <b>and</b> height is
    /// smaller than <see cref="MinHeight"/>. In both modes the idea with filtering by objects'
    /// maximum size is the same as filtering by objects' minimum size.</para>
    /// 
    /// <para>Default value is set to <see langword="false"/>, what means uncoupled filtering by size.</para>
    /// </remarks>
    /// 
    public bool CoupledSizeFiltering
    {
      get { return coupledSizeFiltering; }
      set { coupledSizeFiltering = value; }
    }

    /// <summary>
    /// Minimum allowed width of blob.
    /// </summary>
    /// 
    /// <remarks><para>The property specifies minimum object's width acceptable by blob counting
    /// routine and has power only when <see cref="FilterBlobs"/> property is set to
    /// <see langword="true"/> and <see cref="BlobsFilter">custom blobs' filter</see> is
    /// set to <see langword="null"/>.</para>
    /// 
    /// <para>See documentation to <see cref="CoupledSizeFiltering"/> for additional information.</para>
    /// </remarks>
    /// 
    public int MinWidth
    {
      get { return minWidth; }
      set { minWidth = value; }
    }

    /// <summary>
    /// Minimum allowed height of blob.
    /// </summary>
    /// 
    /// <remarks><para>The property specifies minimum object's height acceptable by blob counting
    /// routine and has power only when <see cref="FilterBlobs"/> property is set to
    /// <see langword="true"/> and <see cref="BlobsFilter">custom blobs' filter</see> is
    /// set to <see langword="null"/>.</para>
    /// 
    /// <para>See documentation to <see cref="CoupledSizeFiltering"/> for additional information.</para>
    /// </remarks>
    /// 
    public int MinHeight
    {
      get { return minHeight; }
      set { minHeight = value; }
    }

    /// <summary>
    /// Maximum allowed width of blob.
    /// </summary>
    /// 
    /// <remarks><para>The property specifies maximum object's width acceptable by blob counting
    /// routine and has power only when <see cref="FilterBlobs"/> property is set to
    /// <see langword="true"/> and <see cref="BlobsFilter">custom blobs' filter</see> is
    /// set to <see langword="null"/>.</para>
    /// 
    /// <para>See documentation to <see cref="CoupledSizeFiltering"/> for additional information.</para>
    /// </remarks>
    /// 
    public int MaxWidth
    {
      get { return maxWidth; }
      set { maxWidth = value; }
    }

    /// <summary>
    /// Maximum allowed height of blob.
    /// </summary>
    /// 
    /// <remarks><para>The property specifies maximum object's height acceptable by blob counting
    /// routine and has power only when <see cref="FilterBlobs"/> property is set to
    /// <see langword="true"/> and <see cref="BlobsFilter">custom blobs' filter</see> is
    /// set to <see langword="null"/>.</para>
    /// 
    /// <para>See documentation to <see cref="CoupledSizeFiltering"/> for additional information.</para>
    /// </remarks>
    /// 
    public int MaxHeight
    {
      get { return maxHeight; }
      set { maxHeight = value; }
    }

    /// <summary>
    /// Custom blobs' filter to use.
    /// </summary>
    /// 
    /// <remarks><para>The property specifies custom blobs' filtering routine to use. It has
    /// effect only in the case if <see cref="FilterBlobs"/> property is set to <see langword="true"/>.</para>
    /// 
    /// <para><note>When custom blobs' filtering routine is set, it has priority over default filtering done
    /// with <see cref="MinWidth"/>, <see cref="MinHeight"/>, <see cref="MaxWidth"/> and <see cref="MaxHeight"/>.</note></para>
    /// </remarks>
    /// 
    public IBlobsFilter BlobsFilter
    {
      get { return filter; }
      set { filter = value; }
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="BlobCounterBase"/> class.
    /// </summary>
    /// 
    /// <remarks>Creates new instance of the <see cref="BlobCounterBase"/> class with
    /// an empty objects map. Before using methods, which provide information about blobs
    /// or extract them, the <see cref="ProcessImage(Bitmap)"/>,
    /// <see cref="ProcessImage(BitmapData)"/> or <see cref="ProcessImage(UnmanagedImage)"/>
    /// method should be called to collect objects map.</remarks>
    /// 
    public BlobCounterBase() { }

    /// <summary>
    /// Initializes a new instance of the <see cref="BlobCounterBase"/> class.
    /// </summary>
    /// 
    /// <param name="image">Binary image to look for objects in.</param>
    /// 
    /// <remarks>Creates new instance of the <see cref="BlobCounterBase"/> class with
    /// initialized objects map built by calling <see cref="ProcessImage(Bitmap)"/> method.</remarks>
    /// 
    public BlobCounterBase(Bitmap image)
    {
      ProcessImage(image);
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="BlobCounterBase"/> class.
    /// </summary>
    /// 
    /// <param name="imageData">Binary image data to look for objects in.</param>
    /// 
    /// <remarks>Creates new instance of the <see cref="BlobCounterBase"/> class with
    /// initialized objects map built by calling <see cref="ProcessImage(BitmapData)"/> method.</remarks>
    /// 
    public BlobCounterBase(BitmapData imageData)
    {
      ProcessImage(imageData);
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="BlobCounterBase"/> class.
    /// </summary>
    /// 
    /// <param name="image">Unmanaged binary image to look for objects in.</param>
    /// 
    /// <remarks>Creates new instance of the <see cref="BlobCounterBase"/> class with
    /// initialized objects map built by calling <see cref="ProcessImage(UnmanagedImage)"/> method.</remarks>
    /// 
    public BlobCounterBase(UnmanagedImage image)
    {
      ProcessImage(image);
    }

    /// <summary>
    /// Build objects map.
    /// </summary>
    /// 
    /// <param name="image">Source binary image.</param>
    /// 
    /// <remarks><para>Processes the image and builds objects map, which is used later to extracts blobs.</para></remarks>
    /// 
    /// <exception cref="UnsupportedImageFormatException">Unsupported pixel format of the source image.</exception>
    /// 
    public void ProcessImage(Bitmap image)
    {
      // lock source bitmap data
      BitmapData imageData = image.LockBits(
          new Rectangle(0, 0, image.Width, image.Height),
          ImageLockMode.ReadOnly, image.PixelFormat);

      try
      {
        // process image
        ProcessImage(imageData);
      }
      finally
      {
        // unlock source image
        image.UnlockBits(imageData);
      }
    }

    /// <summary>
    /// Build objects map.
    /// </summary>
    /// 
    /// <param name="imageData">Source binary image data.</param>
    /// 
    /// <remarks><para>Processes the image and builds objects map, which is used later to extracts blobs.</para></remarks>
    /// 
    /// <exception cref="UnsupportedImageFormatException">Unsupported pixel format of the source image.</exception>
    /// 
    public void ProcessImage(BitmapData imageData)
    {
      // do actual objects map building
      ProcessImage(new UnmanagedImage(imageData));
    }

    /// <summary>
    /// Build object map from raw image data.
    /// </summary>
    /// 
    /// <param name="image">Source unmanaged binary image data.</param>
    /// 
    /// <remarks><para>Processes the image and builds objects map, which is used later to extracts blobs.</para></remarks>
    /// 
    /// <exception cref="UnsupportedImageFormatException">Unsupported pixel format of the source image.</exception>
    /// <exception cref="InvalidImagePropertiesException">Thrown by some inherited classes if some image property other
    /// than the pixel format is not supported. See that class's documentation or the exception message for details.</exception>
    /// 
    public void ProcessImage(UnmanagedImage image)
    {
      imageWidth = image.Width;
      imageHeight = image.Height;

      // do actual objects map building
      BuildObjectsMap(image);

      // collect information about blobs
      CollectObjectsInfo(image);

      // filter blobs by size if required
      if (filterBlobs)
      {
        // labels remapping array
        int[] labelsMap = new int[objectsCount + 1];
        for (int i = 1; i <= objectsCount; i++)
        {
          labelsMap[i] = i;
        }

        // check dimension of all objects and filter them
        int objectsToRemove = 0;

        if (filter == null)
        {
          for (int i = objectsCount - 1; i >= 0; i--)
          {
            int blobWidth = blobs[i].Rectangle.Width;
            int blobHeight = blobs[i].Rectangle.Height;

            if (coupledSizeFiltering == false)
            {
              // uncoupled filtering
              if (
                  (blobWidth < minWidth) || (blobHeight < minHeight) ||
                  (blobWidth > maxWidth) || (blobHeight > maxHeight))
              {
                labelsMap[i + 1] = 0;
                objectsToRemove++;
                blobs.RemoveAt(i);
              }
            }
            else
            {
              // coupled filtering
              if (
                  ((blobWidth < minWidth) && (blobHeight < minHeight)) ||
                  ((blobWidth > maxWidth) && (blobHeight > maxHeight)))
              {
                labelsMap[i + 1] = 0;
                objectsToRemove++;
                blobs.RemoveAt(i);
              }
            }
          }
        }
        else
        {
          for (int i = objectsCount - 1; i >= 0; i--)
          {
            if (!filter.Check(blobs[i]))
            {
              labelsMap[i + 1] = 0;
              objectsToRemove++;
              blobs.RemoveAt(i);
            }
          }
        }

        // update labels remapping array
        int label = 0;
        for (int i = 1; i <= objectsCount; i++)
        {
          if (labelsMap[i] != 0)
          {
            label++;
            // update remapping array
            labelsMap[i] = label;
          }
        }

        // repair object labels
        for (int i = 0, n = objectLabels.Length; i < n; i++)
        {
          objectLabels[i] = labelsMap[objectLabels[i]];
        }

        objectsCount -= objectsToRemove;

        // repair IDs
        for (int i = 0, n = blobs.Count; i < n; i++)
        {
          blobs[i].ID = i + 1;
        }
      }

      // do we need to sort the list?
      if (objectsOrder != ObjectsOrder.None)
      {
        blobs.Sort(new BlobsSorter(objectsOrder));
      }
    }

    /// <summary>
    /// Get objects' rectangles.
    /// </summary>
    /// 
    /// <returns>Returns array of objects' rectangles.</returns>
    /// 
    /// <remarks>The method returns array of objects rectangles. Before calling the
    /// method, the <see cref="ProcessImage(Bitmap)"/>, <see cref="ProcessImage(BitmapData)"/>
    /// or <see cref="ProcessImage(UnmanagedImage)"/> method should be called, which will
    /// build objects map.</remarks>
    /// 
    /// <exception cref="ApplicationException">No image was processed before, so objects' rectangles
    /// can not be collected.</exception>
    /// 
    public Rectangle[] GetObjectsRectangles()
    {
      // check if objects map was collected
      if (objectLabels == null)
        throw new ApplicationException("Image should be processed before to collect objects map.");

      Rectangle[] rects = new Rectangle[objectsCount];

      for (int i = 0; i < objectsCount; i++)
      {
        rects[i] = blobs[i].Rectangle;
      }

      return rects;
    }

    /// <summary>
    /// Get objects' information.
    /// </summary>
    /// 
    /// <returns>Returns array of partially initialized blobs (without <see cref="Blob.Image"/> property initialized).</returns>
    /// 
    /// <remarks><para>By the amount of provided information, the method is between <see cref="GetObjectsRectangles"/> and
    /// <see cref="GetObjects( UnmanagedImage, bool )"/> methods. The method provides array of blobs without initialized their image.
    /// Blob's image may be extracted later using <see cref="ExtractBlobsImage( Bitmap, Blob, bool )"/>
    /// or <see cref="ExtractBlobsImage( UnmanagedImage, Blob, bool )"/> method.
    /// </para></remarks>
    /// 
    /// <example>
    /// <code>
    /// // create blob counter and process image
    /// BlobCounter bc = new BlobCounter( sourceImage );
    /// // specify sort order
    /// bc.ObjectsOrder = ObjectsOrder.Size;
    /// // get objects' information (blobs without image)
    /// Blob[] blobs = bc.GetObjectInformation( );
    /// // process blobs
    /// foreach ( Blob blob in blobs )
    /// {
    ///     // check blob's properties
    ///     if ( blob.Rectangle.Width > 50 )
    ///     {
    ///         // the blob looks interesting, let's extract it
    ///         bc.ExtractBlobsImage( sourceImage, blob );
    ///     }
    /// }
    /// </code>
    /// </example>
    /// 
    /// <exception cref="ApplicationException">No image was processed before, so objects' information
    /// can not be collected.</exception>
    /// 
    public Blob[] GetObjectsInformation()
    {
      // check if objects map was collected
      if (objectLabels == null)
        throw new ApplicationException("Image should be processed before to collect objects map.");

      Blob[] blobsToReturn = new Blob[objectsCount];

      // create each blob
      for (int k = 0; k < objectsCount; k++)
      {
        blobsToReturn[k] = new Blob(blobs[k]);
      }

      return blobsToReturn;
    }

    /// <summary>
    /// Get blobs.
    /// </summary>
    /// 
    /// <param name="image">Source image to extract objects from.</param>
    /// 
    /// <returns>Returns array of blobs.</returns>
    /// <param name="extractInOriginalSize">Specifies size of blobs' image to extract.
    /// If set to <see langword="true"/> each blobs' image will have the same size as
    /// the specified image. If set to <see langword="false"/> each blobs' image will
    /// have the size of its blob.</param>
    ///
    /// <remarks><para>The method returns array of blobs. Before calling the
    /// method, the <see cref="ProcessImage(Bitmap)"/>, <see cref="ProcessImage(BitmapData)"/>
    /// or <see cref="ProcessImage(UnmanagedImage)"/> method should be called, which will build
    /// objects map.</para>
    /// 
    /// <para>The method supports 24/32 bpp color and 8 bpp indexed grayscale images.</para>
    /// </remarks>
    /// 
    /// <exception cref="UnsupportedImageFormatException">Unsupported pixel format of the provided image.</exception>
    /// <exception cref="ApplicationException">No image was processed before, so objects
    /// can not be collected.</exception>
    /// 
    public Blob[] GetObjects(Bitmap image, bool extractInOriginalSize)
    {
      Blob[] blobs = null;
      // lock source bitmap data
      BitmapData imageData = image.LockBits(
          new Rectangle(0, 0, image.Width, image.Height),
          ImageLockMode.ReadOnly, image.PixelFormat);

      try
      {
        // process image
        blobs = GetObjects(new UnmanagedImage(imageData), extractInOriginalSize);
      }
      finally
      {
        // unlock source images
        image.UnlockBits(imageData);
      }
      return blobs;
    }

    /// <summary>
    /// Get blobs.
    /// </summary>
    /// 
    /// <param name="image">Source unmanaged image to extract objects from.</param>
    /// <param name="extractInOriginalSize">Specifies size of blobs' image to extract.
    /// If set to <see langword="true"/> each blobs' image will have the same size as
    /// the specified image. If set to <see langword="false"/> each blobs' image will
    /// have the size of its blob.</param>
    /// 
    /// <returns>Returns array of blobs.</returns>
    /// 
    /// <remarks><para>The method returns array of blobs. Before calling the
    /// method, the <see cref="ProcessImage(Bitmap)"/>, <see cref="ProcessImage(BitmapData)"/>
    /// or <see cref="ProcessImage(UnmanagedImage)"/> method should be called, which will build
    /// objects map.</para>
    /// 
    /// <para>The method supports 24/32 bpp color and 8 bpp indexed grayscale images.</para>
    /// </remarks>
    ///
    /// <exception cref="UnsupportedImageFormatException">Unsupported pixel format of the provided image.</exception>
    /// <exception cref="ApplicationException">No image was processed before, so objects
    /// can not be collected.</exception>
    /// 
    public Blob[] GetObjects(UnmanagedImage image, bool extractInOriginalSize)
    {
      // check if objects map was collected
      if (objectLabels == null)
        throw new ApplicationException("Image should be processed before to collect objects map.");

      if (
          (image.PixelFormat != PixelFormat.Format24bppRgb) &&
          (image.PixelFormat != PixelFormat.Format8bppIndexed) &&
          (image.PixelFormat != PixelFormat.Format32bppArgb) &&
          (image.PixelFormat != PixelFormat.Format32bppRgb) &&
          (image.PixelFormat != PixelFormat.Format32bppPArgb)
          )
        throw new UnsupportedImageFormatException("Unsupported pixel format of the provided image.");

      // image size
      int width = image.Width;
      int height = image.Height;
      int srcStride = image.Stride;
      int pixelSize = Bitmap.GetPixelFormatSize(image.PixelFormat) / 8;

      Blob[] objects = new Blob[objectsCount];

      // create each image
      for (int k = 0; k < objectsCount; k++)
      {
        int objectWidth = blobs[k].Rectangle.Width;
        int objectHeight = blobs[k].Rectangle.Height;

        int blobImageWidth = (extractInOriginalSize) ? width : objectWidth;
        int blobImageHeight = (extractInOriginalSize) ? height : objectHeight;

        int xmin = blobs[k].Rectangle.X;
        int xmax = xmin + objectWidth - 1;
        int ymin = blobs[k].Rectangle.Y;
        int ymax = ymin + objectHeight - 1;

        int label = blobs[k].ID;

        // create new image
        UnmanagedImage dstImage = UnmanagedImage.Create(blobImageWidth, blobImageHeight, image.PixelFormat);

        // copy image
        unsafe
        {
          byte* src = (byte*)image.ImageData.ToPointer() + ymin * srcStride + xmin * pixelSize;
          byte* dst = (byte*)dstImage.ImageData.ToPointer();
          int p = ymin * width + xmin;

          if (extractInOriginalSize)
          {
            // allign destination pointer also
            dst += ymin * dstImage.Stride + xmin * pixelSize;
          }

          int srcOffset = srcStride - objectWidth * pixelSize;
          int dstOffset = dstImage.Stride - objectWidth * pixelSize;
          int labelsOffset = width - objectWidth;

          // for each line
          for (int y = ymin; y <= ymax; y++)
          {
            // copy each pixel
            for (int x = xmin; x <= xmax; x++, p++, dst += pixelSize, src += pixelSize)
            {
              if (objectLabels[p] == label)
              {
                // copy pixel
                *dst = *src;

                if (pixelSize > 1)
                {
                  dst[1] = src[1];
                  dst[2] = src[2];

                  if (pixelSize > 3)
                  {
                    dst[3] = src[3];
                  }
                }
              }
            }
            src += srcOffset;
            dst += dstOffset;
            p += labelsOffset;
          }
        }

        objects[k] = new Blob(blobs[k]);
        objects[k].Image = dstImage;
        objects[k].OriginalSize = extractInOriginalSize;
      }

      return objects;
    }

    /// <summary>
    /// Extract blob's image.
    /// </summary>
    /// 
    /// <param name="image">Source image to extract blob's image from.</param>
    /// <param name="blob">Blob which is required to be extracted.</param>
    /// <param name="extractInOriginalSize">Specifies size of blobs' image to extract.
    /// If set to <see langword="true"/> each blobs' image will have the same size as
    /// the specified image. If set to <see langword="false"/> each blobs' image will
    /// have the size of its blob.</param>
    ///
    /// <remarks><para>The method is used to extract image of partially initialized blob, which
    /// was provided by <see cref="GetObjectsInformation"/> method. Before calling the
    /// method, the <see cref="ProcessImage(Bitmap)"/>, <see cref="ProcessImage(BitmapData)"/>
    /// or <see cref="ProcessImage(UnmanagedImage)"/> method should be called, which will build
    /// objects map.</para>
    /// 
    /// <para>The method supports 24/32 bpp color and 8 bpp indexed grayscale images.</para>
    /// </remarks>
    /// 
    /// <exception cref="UnsupportedImageFormatException">Unsupported pixel format of the provided image.</exception>
    /// <exception cref="ApplicationException">No image was processed before, so blob
    /// can not be extracted.</exception>
    /// 
    public void ExtractBlobsImage(Bitmap image, Blob blob, bool extractInOriginalSize)
    {
      // lock source bitmap data
      BitmapData imageData = image.LockBits(
          new Rectangle(0, 0, image.Width, image.Height),
          ImageLockMode.ReadOnly, image.PixelFormat);

      try
      {
        // process image
        ExtractBlobsImage(new UnmanagedImage(imageData), blob, extractInOriginalSize);
      }
      finally
      {
        // unlock source images
        image.UnlockBits(imageData);
      }
    }

    /// <summary>
    /// Extract blob's image.
    /// </summary>
    /// 
    /// <param name="image">Source unmanaged image to extract blob's image from.</param>
    /// <param name="blob">Blob which is required to be extracted.</param>
    /// <param name="extractInOriginalSize">Specifies size of blobs' image to extract.
    /// If set to <see langword="true"/> each blobs' image will have the same size as
    /// the specified image. If set to <see langword="false"/> each blobs' image will
    /// have the size of its blob.</param>
    ///
    /// <remarks><para>The method is used to extract image of partially initialized blob, which
    /// was provided by <see cref="GetObjectsInformation"/> method. Before calling the
    /// method, the <see cref="ProcessImage(Bitmap)"/>, <see cref="ProcessImage(BitmapData)"/>
    /// or <see cref="ProcessImage(UnmanagedImage)"/> method should be called, which will build
    /// objects map.</para>
    /// 
    /// <para>The method supports 24/32 bpp color and 8 bpp indexed grayscale images.</para>
    /// </remarks>
    /// 
    /// <exception cref="UnsupportedImageFormatException">Unsupported pixel format of the provided image.</exception>
    /// <exception cref="ApplicationException">No image was processed before, so blob
    /// can not be extracted.</exception>
    /// 
    public void ExtractBlobsImage(UnmanagedImage image, Blob blob, bool extractInOriginalSize)
    {
      // check if objects map was collected
      if (objectLabels == null)
        throw new ApplicationException("Image should be processed before to collect objects map.");

      if (
          (image.PixelFormat != PixelFormat.Format24bppRgb) &&
          (image.PixelFormat != PixelFormat.Format8bppIndexed) &&
          (image.PixelFormat != PixelFormat.Format32bppArgb) &&
          (image.PixelFormat != PixelFormat.Format32bppRgb) &&
          (image.PixelFormat != PixelFormat.Format32bppPArgb)
          )
        throw new UnsupportedImageFormatException("Unsupported pixel format of the provided image.");

      // image size
      int width = image.Width;
      int height = image.Height;
      int srcStride = image.Stride;
      int pixelSize = Bitmap.GetPixelFormatSize(image.PixelFormat) / 8;

      int objectWidth = blob.Rectangle.Width;
      int objectHeight = blob.Rectangle.Height;

      int blobImageWidth = (extractInOriginalSize) ? width : objectWidth;
      int blobImageHeight = (extractInOriginalSize) ? height : objectHeight;

      int xmin = blob.Rectangle.Left;
      int xmax = xmin + objectWidth - 1;
      int ymin = blob.Rectangle.Top;
      int ymax = ymin + objectHeight - 1;

      int label = blob.ID;

      // create new image
      blob.Image = UnmanagedImage.Create(blobImageWidth, blobImageHeight, image.PixelFormat);
      blob.OriginalSize = extractInOriginalSize;

      // copy image
      unsafe
      {
        byte* src = (byte*)image.ImageData.ToPointer() + ymin * srcStride + xmin * pixelSize;
        byte* dst = (byte*)blob.Image.ImageData.ToPointer();
        int p = ymin * width + xmin;

        if (extractInOriginalSize)
        {
          // allign destination pointer also
          dst += ymin * blob.Image.Stride + xmin * pixelSize;
        }

        int srcOffset = srcStride - objectWidth * pixelSize;
        int dstOffset = blob.Image.Stride - objectWidth * pixelSize;
        int labelsOffset = width - objectWidth;

        // for each line
        for (int y = ymin; y <= ymax; y++)
        {
          // copy each pixel
          for (int x = xmin; x <= xmax; x++, p++, dst += pixelSize, src += pixelSize)
          {
            if (objectLabels[p] == label)
            {
              // copy pixel
              *dst = *src;

              if (pixelSize > 1)
              {
                dst[1] = src[1];
                dst[2] = src[2];

                if (pixelSize > 3)
                {
                  dst[3] = src[3];
                }
              }
            }
          }
          src += srcOffset;
          dst += dstOffset;
          p += labelsOffset;
        }
      }
    }

    /// <summary>
    /// Get list of points on the left and right edges of the blob.
    /// </summary>
    /// 
    /// <param name="blob">Blob to collect edge points for.</param>
    /// <param name="leftEdge">List of points on the left edge of the blob.</param>
    /// <param name="rightEdge">List of points on the right edge of the blob.</param>
    /// 
    /// <remarks><para>The method scans each line of the blob and finds the most left and the
    /// most right points for it adding them to appropriate lists. The method may be very
    /// useful in conjunction with different routines from Geometry,
    /// which allow finding convex hull or quadrilateral's corners.</para>
    /// 
    /// <para><note>Both lists of points are sorted by Y coordinate - points with smaller Y
    /// value go first.</note></para>
    /// </remarks>
    /// 
    /// <exception cref="ApplicationException">No image was processed before, so blob
    /// can not be extracted.</exception>
    /// 
    public void GetBlobsLeftAndRightEdges(Blob blob, out List<IntPoint> leftEdge, out List<IntPoint> rightEdge)
    {
      // check if objects map was collected
      if (objectLabels == null)
        throw new ApplicationException("Image should be processed before to collect objects map.");

      leftEdge = new List<IntPoint>();
      rightEdge = new List<IntPoint>();

      int xmin = blob.Rectangle.Left;
      int xmax = xmin + blob.Rectangle.Width - 1;
      int ymin = blob.Rectangle.Top;
      int ymax = ymin + blob.Rectangle.Height - 1;

      int label = blob.ID;

      // for each line
      for (int y = ymin; y <= ymax; y++)
      {
        // scan from left to right
        int p = y * imageWidth + xmin;
        for (int x = xmin; x <= xmax; x++, p++)
        {
          if (objectLabels[p] == label)
          {
            leftEdge.Add(new IntPoint(x, y));
            break;
          }
        }

        // scan from right to left
        p = y * imageWidth + xmax;
        for (int x = xmax; x >= xmin; x--, p--)
        {
          if (objectLabels[p] == label)
          {
            rightEdge.Add(new IntPoint(x, y));
            break;
          }
        }
      }
    }

    /// <summary>
    /// Get list of points on the top and bottom edges of the blob.
    /// </summary>
    /// 
    /// <param name="blob">Blob to collect edge points for.</param>
    /// <param name="topEdge">List of points on the top edge of the blob.</param>
    /// <param name="bottomEdge">List of points on the bottom edge of the blob.</param>
    /// 
    /// <remarks><para>The method scans each column of the blob and finds the most top and the
    /// most bottom points for it adding them to appropriate lists. The method may be very
    /// useful in conjunction with different routines from Geometry,
    /// which allow finding convex hull or quadrilateral's corners.</para>
    /// 
    /// <para><note>Both lists of points are sorted by X coordinate - points with smaller X
    /// value go first.</note></para>
    /// </remarks>
    /// 
    /// <exception cref="ApplicationException">No image was processed before, so blob
    /// can not be extracted.</exception>
    /// 
    public void GetBlobsTopAndBottomEdges(Blob blob, out List<IntPoint> topEdge, out List<IntPoint> bottomEdge)
    {
      // check if objects map was collected
      if (objectLabels == null)
        throw new ApplicationException("Image should be processed before to collect objects map.");

      topEdge = new List<IntPoint>();
      bottomEdge = new List<IntPoint>();

      int xmin = blob.Rectangle.Left;
      int xmax = xmin + blob.Rectangle.Width - 1;
      int ymin = blob.Rectangle.Top;
      int ymax = ymin + blob.Rectangle.Height - 1;

      int label = blob.ID;

      // for each column
      for (int x = xmin; x <= xmax; x++)
      {
        // scan from top to bottom
        int p = ymin * imageWidth + x;
        for (int y = ymin; y <= ymax; y++, p += imageWidth)
        {
          if (objectLabels[p] == label)
          {
            topEdge.Add(new IntPoint(x, y));
            break;
          }
        }

        // scan from bottom to top
        p = ymax * imageWidth + x;
        for (int y = ymax; y >= ymin; y--, p -= imageWidth)
        {
          if (objectLabels[p] == label)
          {
            bottomEdge.Add(new IntPoint(x, y));
            break;
          }
        }
      }
    }

    /// <summary>
    /// Get list of object's edge points.
    /// </summary>
    /// 
    /// <param name="blob">Blob to collect edge points for.</param>
    /// 
    /// <returns>Returns unsorted list of blob's edge points.</returns>
    /// 
    /// <remarks><para>The method scans each row and column of the blob and finds the
    /// most top/bottom/left/right points. The method returns similar result as if results of
    /// both <see cref="GetBlobsLeftAndRightEdges"/> and <see cref="GetBlobsTopAndBottomEdges"/>
    /// methods were combined, but each edge point occurs only once in the list.</para>
    /// 
    /// <para><note>Edge points in the returned list are not ordered. This makes the list unusable
    /// for visualization with methods, which draw polygon or poly-line. But the returned list
    /// can be used with such algorithms, like convex hull search, shape analyzer, etc.</note></para>
    /// </remarks>
    /// 
    /// <exception cref="ApplicationException">No image was processed before, so blob
    /// can not be extracted.</exception>
    /// 
    public List<IntPoint> GetBlobsEdgePoints(Blob blob)
    {
      // check if objects map was collected
      if (objectLabels == null)
        throw new ApplicationException("Image should be processed before to collect objects map.");

      List<IntPoint> edgePoints = new List<IntPoint>();

      int xmin = blob.Rectangle.Left;
      int xmax = xmin + blob.Rectangle.Width - 1;
      int ymin = blob.Rectangle.Top;
      int ymax = ymin + blob.Rectangle.Height - 1;

      int label = blob.ID;

      // array of already processed points on left/right edges
      // (index in these arrays represent Y coordinate, but value - X coordinate)
      int[] leftProcessedPoints = new int[blob.Rectangle.Height];
      int[] rightProcessedPoints = new int[blob.Rectangle.Height];

      // for each line
      for (int y = ymin; y <= ymax; y++)
      {
        // scan from left to right
        int p = y * imageWidth + xmin;
        for (int x = xmin; x <= xmax; x++, p++)
        {
          if (objectLabels[p] == label)
          {
            edgePoints.Add(new IntPoint(x, y));
            leftProcessedPoints[y - ymin] = x;
            break;
          }
        }

        // scan from right to left
        p = y * imageWidth + xmax;
        for (int x = xmax; x >= xmin; x--, p--)
        {
          if (objectLabels[p] == label)
          {
            // avoid adding the point we already have
            if (leftProcessedPoints[y - ymin] != x)
            {
              edgePoints.Add(new IntPoint(x, y));
            }
            rightProcessedPoints[y - ymin] = x;
            break;
          }
        }
      }

      // for each column
      for (int x = xmin; x <= xmax; x++)
      {
        // scan from top to bottom
        int p = ymin * imageWidth + x;
        for (int y = ymin, y0 = 0; y <= ymax; y++, y0++, p += imageWidth)
        {
          if (objectLabels[p] == label)
          {
            // avoid adding the point we already have
            if ((leftProcessedPoints[y0] != x) &&
                 (rightProcessedPoints[y0] != x))
            {
              edgePoints.Add(new IntPoint(x, y));
            }
            break;
          }
        }

        // scan from bottom to top
        p = ymax * imageWidth + x;
        for (int y = ymax, y0 = ymax - ymin; y >= ymin; y--, y0--, p -= imageWidth)
        {
          if (objectLabels[p] == label)
          {
            // avoid adding the point we already have
            if ((leftProcessedPoints[y0] != x) &&
                 (rightProcessedPoints[y0] != x))
            {
              edgePoints.Add(new IntPoint(x, y));
            }
            break;
          }
        }
      }

      return edgePoints;
    }

    /// <summary>
    /// Actual objects map building.
    /// </summary>
    /// 
    /// <param name="image">Unmanaged image to process.</param>
    /// 
    /// <remarks><note>By the time this method is called bitmap's pixel format is not
    /// yet checked, so this should be done by the class inheriting from the base class.
    /// <see cref="imageWidth"/> and <see cref="imageHeight"/> members are initialized
    /// before the method is called, so these members may be used safely.</note></remarks>
    /// 
    protected abstract void BuildObjectsMap(UnmanagedImage image);


    #region Private Methods - Collecting objects' rectangles

    // Collect objects' rectangles
    private unsafe void CollectObjectsInfo(UnmanagedImage image)
    {
      int i = 0, label;

      // create object coordinates arrays
      int[] x1 = new int[objectsCount + 1];
      int[] y1 = new int[objectsCount + 1];
      int[] x2 = new int[objectsCount + 1];
      int[] y2 = new int[objectsCount + 1];

      int[] area = new int[objectsCount + 1];
      long[] xc = new long[objectsCount + 1];
      long[] yc = new long[objectsCount + 1];

      long[] meanR = new long[objectsCount + 1];
      long[] meanG = new long[objectsCount + 1];
      long[] meanB = new long[objectsCount + 1];

      long[] stdDevR = new long[objectsCount + 1];
      long[] stdDevG = new long[objectsCount + 1];
      long[] stdDevB = new long[objectsCount + 1];

      for (int j = 1; j <= objectsCount; j++)
      {
        x1[j] = imageWidth;
        y1[j] = imageHeight;
      }

      byte* src = (byte*)image.ImageData.ToPointer();

      if (image.PixelFormat == PixelFormat.Format8bppIndexed)
      {
        int offset = image.Stride - imageWidth;
        byte g; // pixel's grey value

        // walk through labels array
        for (int y = 0; y < imageHeight; y++)
        {
          for (int x = 0; x < imageWidth; x++, i++, src++)
          {
            // get current label
            label = objectLabels[i];

            // skip unlabeled pixels
            if (label == 0)
              continue;

            // check and update all coordinates

            if (x < x1[label])
            {
              x1[label] = x;
            }
            if (x > x2[label])
            {
              x2[label] = x;
            }
            if (y < y1[label])
            {
              y1[label] = y;
            }
            if (y > y2[label])
            {
              y2[label] = y;
            }

            area[label]++;
            xc[label] += x;
            yc[label] += y;

            g = *src;
            meanG[label] += g;
            stdDevG[label] += g * g;
          }

          src += offset;
        }

        for (int j = 1; j <= objectsCount; j++)
        {
          meanR[j] = meanB[j] = meanG[j];
          stdDevR[j] = stdDevB[j] = meanG[j];
        }
      }
      else
      {
        // color images
        int pixelSize = Bitmap.GetPixelFormatSize(image.PixelFormat) / 8;
        int offset = image.Stride - imageWidth * pixelSize;
        byte r, g, b; // RGB value

        // walk through labels array
        for (int y = 0; y < imageHeight; y++)
        {
          for (int x = 0; x < imageWidth; x++, i++, src += pixelSize)
          {
            // get current label
            label = objectLabels[i];

            // skip unlabeled pixels
            if (label == 0)
              continue;

            // check and update all coordinates

            if (x < x1[label])
            {
              x1[label] = x;
            }
            if (x > x2[label])
            {
              x2[label] = x;
            }
            if (y < y1[label])
            {
              y1[label] = y;
            }
            if (y > y2[label])
            {
              y2[label] = y;
            }

            area[label]++;
            xc[label] += x;
            yc[label] += y;

            r = src[RGB.R];
            g = src[RGB.G];
            b = src[RGB.B];

            meanR[label] += r;
            meanG[label] += g;
            meanB[label] += b;

            stdDevR[label] += r * r;
            stdDevG[label] += g * g;
            stdDevB[label] += b * b;
          }

          src += offset;
        }
      }

      // create blobs
      blobs.Clear();

      for (int j = 1; j <= objectsCount; j++)
      {
        int blobArea = area[j];

        Blob blob = new Blob(j, new Rectangle(x1[j], y1[j], x2[j] - x1[j] + 1, y2[j] - y1[j] + 1));
        blob.Area = blobArea;
        blob.Fullness = (double)blobArea / ((x2[j] - x1[j] + 1) * (y2[j] - y1[j] + 1));
        blob.CenterOfGravity = new IntPoint((int)(xc[j] / blobArea), (int)(yc[j] / blobArea));
        blob.ColorMean = Color.FromArgb((byte)(meanR[j] / blobArea), (byte)(meanG[j] / blobArea), (byte)(meanB[j] / blobArea));
        blob.ColorStdDev = Color.FromArgb(
            (byte)(Math.Sqrt(stdDevR[j] / blobArea - blob.ColorMean.R * blob.ColorMean.R)),
            (byte)(Math.Sqrt(stdDevG[j] / blobArea - blob.ColorMean.G * blob.ColorMean.G)),
            (byte)(Math.Sqrt(stdDevB[j] / blobArea - blob.ColorMean.B * blob.ColorMean.B)));

        blobs.Add(blob);
      }
    }

    // Rectangles' and blobs' sorter
    private class BlobsSorter : System.Collections.Generic.IComparer<Blob>
    {
      private ObjectsOrder order;

      public BlobsSorter(ObjectsOrder order)
      {
        this.order = order;
      }

      public int Compare(Blob a, Blob b)
      {
        Rectangle aRect = a.Rectangle;
        Rectangle bRect = b.Rectangle;

        switch (order)
        {
          case ObjectsOrder.Size: // sort by size

            // the order is changed to descending
            return (bRect.Width * bRect.Height - aRect.Width * aRect.Height);

          case ObjectsOrder.Area: // sort by area
            return b.Area - a.Area;

          case ObjectsOrder.YX:   // YX order

            return ((aRect.Y * 100000 + aRect.X) - (bRect.Y * 100000 + bRect.X));

          case ObjectsOrder.XY:   // XY order

            return ((aRect.X * 100000 + aRect.Y) - (bRect.X * 100000 + bRect.Y));
        }
        return 0;
      }
    }

    #endregion
  }
}
